<!DOCTYPE html>
<html>
<head>
<title>离散数学上复习.md</title>
<meta http-equiv="Content-type" content="text/html;charset=UTF-8">

<style>
/* https://github.com/microsoft/vscode/blob/master/extensions/markdown-language-features/media/markdown.css */
/*---------------------------------------------------------------------------------------------
 *  Copyright (c) Microsoft Corporation. All rights reserved.
 *  Licensed under the MIT License. See License.txt in the project root for license information.
 *--------------------------------------------------------------------------------------------*/

body {
	font-family: var(--vscode-markdown-font-family, -apple-system, BlinkMacSystemFont, "Segoe WPC", "Segoe UI", "Ubuntu", "Droid Sans", sans-serif);
	font-size: var(--vscode-markdown-font-size, 14px);
	padding: 0 26px;
	line-height: var(--vscode-markdown-line-height, 22px);
	word-wrap: break-word;
}

#code-csp-warning {
	position: fixed;
	top: 0;
	right: 0;
	color: white;
	margin: 16px;
	text-align: center;
	font-size: 12px;
	font-family: sans-serif;
	background-color:#444444;
	cursor: pointer;
	padding: 6px;
	box-shadow: 1px 1px 1px rgba(0,0,0,.25);
}

#code-csp-warning:hover {
	text-decoration: none;
	background-color:#007acc;
	box-shadow: 2px 2px 2px rgba(0,0,0,.25);
}

body.scrollBeyondLastLine {
	margin-bottom: calc(100vh - 22px);
}

body.showEditorSelection .code-line {
	position: relative;
}

body.showEditorSelection .code-active-line:before,
body.showEditorSelection .code-line:hover:before {
	content: "";
	display: block;
	position: absolute;
	top: 0;
	left: -12px;
	height: 100%;
}

body.showEditorSelection li.code-active-line:before,
body.showEditorSelection li.code-line:hover:before {
	left: -30px;
}

.vscode-light.showEditorSelection .code-active-line:before {
	border-left: 3px solid rgba(0, 0, 0, 0.15);
}

.vscode-light.showEditorSelection .code-line:hover:before {
	border-left: 3px solid rgba(0, 0, 0, 0.40);
}

.vscode-light.showEditorSelection .code-line .code-line:hover:before {
	border-left: none;
}

.vscode-dark.showEditorSelection .code-active-line:before {
	border-left: 3px solid rgba(255, 255, 255, 0.4);
}

.vscode-dark.showEditorSelection .code-line:hover:before {
	border-left: 3px solid rgba(255, 255, 255, 0.60);
}

.vscode-dark.showEditorSelection .code-line .code-line:hover:before {
	border-left: none;
}

.vscode-high-contrast.showEditorSelection .code-active-line:before {
	border-left: 3px solid rgba(255, 160, 0, 0.7);
}

.vscode-high-contrast.showEditorSelection .code-line:hover:before {
	border-left: 3px solid rgba(255, 160, 0, 1);
}

.vscode-high-contrast.showEditorSelection .code-line .code-line:hover:before {
	border-left: none;
}

img {
	max-width: 100%;
	max-height: 100%;
}

a {
	text-decoration: none;
}

a:hover {
	text-decoration: underline;
}

a:focus,
input:focus,
select:focus,
textarea:focus {
	outline: 1px solid -webkit-focus-ring-color;
	outline-offset: -1px;
}

hr {
	border: 0;
	height: 2px;
	border-bottom: 2px solid;
}

h1 {
	padding-bottom: 0.3em;
	line-height: 1.2;
	border-bottom-width: 1px;
	border-bottom-style: solid;
}

h1, h2, h3 {
	font-weight: normal;
}

table {
	border-collapse: collapse;
}

table > thead > tr > th {
	text-align: left;
	border-bottom: 1px solid;
}

table > thead > tr > th,
table > thead > tr > td,
table > tbody > tr > th,
table > tbody > tr > td {
	padding: 5px 10px;
}

table > tbody > tr + tr > td {
	border-top: 1px solid;
}

blockquote {
	margin: 0 7px 0 5px;
	padding: 0 16px 0 10px;
	border-left-width: 5px;
	border-left-style: solid;
}

code {
	font-family: Menlo, Monaco, Consolas, "Droid Sans Mono", "Courier New", monospace, "Droid Sans Fallback";
	font-size: 1em;
	line-height: 1.357em;
}

body.wordWrap pre {
	white-space: pre-wrap;
}

pre:not(.hljs),
pre.hljs code > div {
	padding: 16px;
	border-radius: 3px;
	overflow: auto;
}

pre code {
	color: var(--vscode-editor-foreground);
	tab-size: 4;
}

/** Theming */

.vscode-light pre {
	background-color: rgba(220, 220, 220, 0.4);
}

.vscode-dark pre {
	background-color: rgba(10, 10, 10, 0.4);
}

.vscode-high-contrast pre {
	background-color: rgb(0, 0, 0);
}

.vscode-high-contrast h1 {
	border-color: rgb(0, 0, 0);
}

.vscode-light table > thead > tr > th {
	border-color: rgba(0, 0, 0, 0.69);
}

.vscode-dark table > thead > tr > th {
	border-color: rgba(255, 255, 255, 0.69);
}

.vscode-light h1,
.vscode-light hr,
.vscode-light table > tbody > tr + tr > td {
	border-color: rgba(0, 0, 0, 0.18);
}

.vscode-dark h1,
.vscode-dark hr,
.vscode-dark table > tbody > tr + tr > td {
	border-color: rgba(255, 255, 255, 0.18);
}

</style>

<style>
/* Tomorrow Theme */
/* http://jmblog.github.com/color-themes-for-google-code-highlightjs */
/* Original theme - https://github.com/chriskempson/tomorrow-theme */

/* Tomorrow Comment */
.hljs-comment,
.hljs-quote {
	color: #8e908c;
}

/* Tomorrow Red */
.hljs-variable,
.hljs-template-variable,
.hljs-tag,
.hljs-name,
.hljs-selector-id,
.hljs-selector-class,
.hljs-regexp,
.hljs-deletion {
	color: #c82829;
}

/* Tomorrow Orange */
.hljs-number,
.hljs-built_in,
.hljs-builtin-name,
.hljs-literal,
.hljs-type,
.hljs-params,
.hljs-meta,
.hljs-link {
	color: #f5871f;
}

/* Tomorrow Yellow */
.hljs-attribute {
	color: #eab700;
}

/* Tomorrow Green */
.hljs-string,
.hljs-symbol,
.hljs-bullet,
.hljs-addition {
	color: #718c00;
}

/* Tomorrow Blue */
.hljs-title,
.hljs-section {
	color: #4271ae;
}

/* Tomorrow Purple */
.hljs-keyword,
.hljs-selector-tag {
	color: #8959a8;
}

.hljs {
	display: block;
	overflow-x: auto;
	color: #4d4d4c;
	padding: 0.5em;
}

.hljs-emphasis {
	font-style: italic;
}

.hljs-strong {
	font-weight: bold;
}
</style>

<style>
/*
 * Markdown PDF CSS
 */

 body {
	font-family: -apple-system, BlinkMacSystemFont, "Segoe WPC", "Segoe UI", "Ubuntu", "Droid Sans", sans-serif, "Meiryo";
	padding: 0 12px;
}

pre {
	background-color: #f8f8f8;
	border: 1px solid #cccccc;
	border-radius: 3px;
	overflow-x: auto;
	white-space: pre-wrap;
	overflow-wrap: break-word;
}

pre:not(.hljs) {
	padding: 23px;
	line-height: 19px;
}

blockquote {
	background: rgba(127, 127, 127, 0.1);
	border-color: rgba(0, 122, 204, 0.5);
}

.emoji {
	height: 1.4em;
}

code {
	font-size: 14px;
	line-height: 19px;
}

/* for inline code */
:not(pre):not(.hljs) > code {
	color: #C9AE75; /* Change the old color so it seems less like an error */
	font-size: inherit;
}

/* Page Break : use <div class="page"/> to insert page break
-------------------------------------------------------- */
.page {
	page-break-after: always;
}

</style>

<script>
  <script src="https://unpkg.com/mermaid/dist/mermaid.min.js"></script>
</script>
</head>
<body>
  <script>
    mermaid.initialize({
      startOnLoad: true,
      theme: document.body.classList.contains('vscode-dark') || document.body.classList.contains('vscode-high-contrast')
          ? 'dark'
          : 'default'
    });
  </script>
<h2 id="%E9%9B%86%E5%90%88%E4%B8%8E%E5%87%BD%E6%95%B0">集合与函数</h2>
<h4 id="21-%E9%9B%86%E5%90%88%E4%B8%8E%E7%AC%9B%E5%8D%A1%E5%B0%94%E7%A7%AF">2.1 集合与笛卡尔积</h4>
<p>一些值得复习的概念</p>
<ul>
<li>证明集合相等：证明互为子集</li>
<li>幂集：
<ul>
<li>定义：S所有子集的集合。所以S是<strong>属于</strong>它的幂集。</li>
<li>用于证明不存在最大的集合（假设存在就取幂集）</li>
<li>基数关系是$n与2^n$</li>
</ul>
</li>
<li><strong>笛卡尔积</strong>：AxB，得到序偶（外层遍历A，内层遍历B）
<ul>
<li>实际意义：举个例子，A表示学生，B表示课程</li>
<li><strong>那么AxB的任一子集都是现实中可能的结果。</strong>（因为事实上某一个学生并不会去遍历所有的课程）；但笛卡尔积是所有可能的结果叠加。</li>
<li>AxB的幂集自然就是所有可能结果的集合。</li>
<li><strong>笛卡尔积的本质是映射</strong>，从两个相对一元映射成一个相对二元。
广义的笛卡尔积可以考虑广义数量，也可以考虑对象
如AxBxC就是把三个一元映射成一个三元。得到结果是(a,b,c)
如(AxB)xC是把一个一元，一个二元映射成一个形如((a,b),c)的结果
<br></li>
<li>AxB的任一子集称为关系，AxA的任一子集称为A上的一个关系。显然，关系 才是现实中可能的结果。</li>
</ul>
</li>
</ul>
<h4 id="22-%E9%9B%86%E5%90%88%E8%BF%90%E7%AE%97">2.2 集合运算</h4>
<p>容斥原理：减去重复计算的。
并集$C$是 满足$A\subset C$和$B\subset C$的最小集合。
交集$C$是 满足$C\subset A$和$C\subset A$的最大集合。</p>
<blockquote>
<p>推广：无穷并与无穷交，要有抽象思维。见书本P90</p>
</blockquote>
<p><strong>差集$A-B$ :在A不在B</strong> ，等效于$A\bigcup \overline{B}$</p>
<p>运算定律：</p>
<ul>
<li>同型结合，不同型分配。</li>
<li>德摩根定律：补集分配or合并，同时联结符号取反</li>
</ul>
<p>证明集合问题方法</p>
<blockquote>
<p>2.1 中提到 证明集合相等：证明互为子集</p>
</blockquote>
<ol>
<li>用定律运算</li>
<li>根据集合性质推进找元素满足的逻辑式子，然后在从逻辑构造回集合</li>
<li>列举法</li>
</ol>
<p>集合的分划：两两不相交，且保证合起来又是原来。
集合的覆盖：不要求两两不相交，但要保证合起来又是原来。</p>
<blockquote>
<p>分划一定是覆盖，反之不成立</p>
</blockquote>
<h4 id="23-%E5%87%BD%E6%95%B0">2.3 函数</h4>
<p>直接认为函数就是一种特殊的 关系。
<strong>函数 不能出现 一对多</strong></p>
<p><strong>$f:A \rightarrow B $是A到B的关系，其中必须保证二元组(a,b)中不会含有重复的第一关键字。同时保证第一关键字一定取遍。</strong></p>
<p>根据关系我们知道，关系不必取遍笛卡尔积，所以，A是定义域，B是陪域，映射的结果/关系的实际结果才是值域。但是A要取遍。</p>
<p><strong>函数的分类</strong>
<strong>单射：一对一</strong>，不保证取完B。要保证函数基本成立，即A取遍，B可以不取遍。
<strong>满射：保证B被取遍</strong>，可以多对一。要保证函数基本成立，即A取遍。
<strong>双射</strong>：既是单射又是满射。
<strong>反函数：只有双射存在反函数</strong>。</p>
<p><strong>函数合成</strong>
$f:A \rightarrow B $         $g:B \rightarrow C$ 合成为$fg$。保证g的值域是f定义域的子集。
<strong>注意顺序，形如复合函数，g是内函数，先映射</strong>
反函数合成相当于映射再逆映射，抵消了，等于没映射。</p>
<p>一些延申的性质与技巧</p>
<ol>
<li>对于$f:A \rightarrow A $，若A有限集，则A单射可以推出A满射（定量角度来看，没有一对多，那么陪域中应该被取完了）；A满射可以推出A单射（定量角度来看，由于定义域一定取完，那么只能一对一射出）
<strong>注意无限集不成立</strong></li>
<li>证明f单射：证明其一对一纯洁性。证明如果函数值相等，则原像唯一。
证明f不单射：找一个多对一反例。
证明f满射：证明B被取遍。
证明f不满射：在B没被取到的反例。</li>
<li>一些简单推理
<ul>
<li>fg单射可以推出g单射。（g先映射，如果g不一对一，再进行f更不会一对一）</li>
<li>fg满射可以推出f满射，（g映射出的甚至都不一定达到了f的完全定义域都能射满，f自己肯定更能射满）</li>
<li><strong>由上述可知 fg双射可以推出g单射 f满射</strong></li>
<li>f单射，g单射 推出 fg单射</li>
<li>f满射，g满射 推出 fg满射</li>
<li>f双射，g双射 推出 fg双射</li>
</ul>
</li>
</ol>
<p>（不重要）部分函数的意思像是如此 $f(x)=\ln x (x&gt;1)$。加了一个限定条件，不加之前是天然定义域x&gt;0,加了变成x&gt;1。不影响A仍然是x&gt;0.</p>
<p>2.4不考</p>
<h4 id="25-%E9%9B%86%E5%90%88%E5%9F%BA%E6%95%B0-%E6%97%A0%E9%99%90%E9%9B%86">2.5 集合基数 无限集</h4>
<p><strong>编号实际上就是建立一种双射。</strong></p>
<p><strong>对于无法直接比较的基数，考虑构造映射关系来比较。</strong></p>
<p>建立A到B的单射。 由于一对一，所以B不必取完。得到$|A|&lt;=|B|$
建立A到B的满射。 由于B被取完，(A取完是因为存在多对一)。得到$|A|&gt;=|B|$
<strong>综上，建立A到B的双射 ,得到$|A|=|B|$</strong></p>
<p>可数集：
有限集：easy
可列无限集：以自然数集为定义出发点，为$\aleph_0$。</p>
<blockquote>
<p>证明可数集有两种方式，本质上都是建立与自然数集的双射，但宏观手段不同</p>
<ol>
<li>列举或者描述出 以一定规律次序编号。见P118</li>
<li>数学函数严谨构造</li>
</ol>
</blockquote>
<p>典题：证明正有理数是可数的（拆成分数列举）。证明自然数+1的集合也是可数。</p>
<p>不可数集：
实数集合就是不可数集合。<strong>它的证明运用了反证，假想出一个合法但是与每个已列都存在相异的事物，来描述它没有被列举出来</strong>.见P119</p>
<p><strong>可列性的打破，连续统假设</strong>：
有限集取幂集一定是有限集。
无限集 取幂集 是唯一打破可列性的手段，也是唯一使基数变化的手段。
比如 自然数集 的幂集基数是$2^{\aleph_0}$,并且不存在$\aleph_0$与$2^{\aleph_0}$的中间态。
可列无限集是最小的无限集。</p>
<blockquote>
<p>连续统假设不能用来证明，但可以用来快速判断。</p>
</blockquote>
<p><strong>一些技巧</strong>：
从定量角度来看：<strong>可以引入$\aleph_0$进行夹逼之类的不等式操作</strong>。
无限集基数&gt;=$\aleph_0$,不可数基数&gt;$\aleph_0$,可数基数&lt;=$\aleph_0$.</p>
<blockquote>
<p>经典的一个技巧是，如果找不到双射，可以找一个单射，再找一个满射。夹逼。也即存在双射，虽然这个双射并不是所找的单满射叠加（但达到了定量的目的）。</p>
</blockquote>
<p>从构造角度来看：<strong>可以尝试构造数学函数/手动编号</strong>。</p>
<p>从逻辑角度来看：运用一些<strong>反证法，逆否命题</strong>等。</p>
<p>一些典题</p>
<ol>
<li>
<p>证明可数集的并也可数。</p>
<blockquote>
<p>先按P119的思路考虑 二元并 的三种情况 ：有限与有限（easy），有限与可列无限（排列先把有限排出来），可列无限与可列无限（捆绑式轮流列举）。
然后用数归推广到多元并。</p>
</blockquote>
</li>
<li>
<p>证明任一无限集一定含有可列无限子集</p>
<blockquote>
<p><strong>对取出的元素进行编号</strong>,取出第一个元素记为a1，第二个元素记为a2，由此构成的集合{a1，a2...}就是可列无限子集c1</p>
</blockquote>
</li>
<li>
<p>证明任一无限集一定有真子集与它基数相等</p>
<blockquote>
<p>作A1=A-{a1}，再同时对A1和A作分划，A被分划成c1和A-c1，A1被分划成c1-{a1}和A-c1.
建立双射从A到A1。如果x属于A-c1，映射到自身，如果x属于c1，映射到下标+1.（比如a2映射到a3，因为缺一个对齐）</p>
</blockquote>
</li>
<li>
<p>证明A不可数，如果$A \subset B$则B不可数</p>
<blockquote>
<ul>
<li>从$\aleph_0$角度证明，A大于$\aleph_0$，B大于等于A，所以B大于$\aleph_0$。</li>
<li>反证： B是可数，那么B可列，那么A能在B中找到，A也可列，矛盾</li>
</ul>
</blockquote>
</li>
<li>
<p>证明可列无限集是最小的无限集。</p>
<blockquote>
<p>转化成证明2.因为得到了 任一 无限集基数&gt;=可列无限子集
思路要打开，想到 只需要证明比 不可数集小 就可以。</p>
</blockquote>
</li>
<li>
<p>证明自然数集删去有限个整数 仍然是可数集</p>
<blockquote>
<ul>
<li>从编号上证明：仍然可以列出，遇到删去的就跳过即可。</li>
<li>从$\aleph_0$角度证明：由子集关系可以知道所求基数&lt;=自然数集基数=$\aleph_0$，为可数集。
反证：是不可数。同 4 ，一样从子集出发。</li>
</ul>
</blockquote>
</li>
<li>
<p>可列无限集任一无限子集也是可列无限</p>
<blockquote>
<ul>
<li>从$\aleph_0$角度证明:夹逼：假设$A \subset B$，A无限大于等于$\aleph_0$，A小于等于B=$\aleph_0$，夹逼完毕。</li>
<li>反证法假设 不是可列无限，但是是无限，只能是不可数。同 4，一样从子集出发。</li>
</ul>
</blockquote>
</li>
<li>
<p>证明R与(0,1)内实数基数相同。并且继续证明可以换成任一一个区间。继续证明可以换成有限个区间并。</p>
<blockquote>
<ul>
<li>由于不可列，只能函数构造。建立一个中心在(0.5,0)的类正切函数得到双射，证毕。
任一区间只需要对正切伸缩变换即可。
有限个区间并则可以夹逼 ： 某一个区间&lt;所求&lt;R,两侧基数上述已经证明过相等。</li>
</ul>
</blockquote>
</li>
</ol>
<h2 id="%E5%85%B3%E7%B3%BB">关系</h2>
<h4 id="51-%E5%85%B3%E7%B3%BB%E5%85%A5%E9%97%A8">5.1 关系入门</h4>
<p>关系是笛卡尔积的子集。关系可以用图来表示，反之也可以用图来理解关系。</p>
<p><strong>关系的性质</strong>
自反性（主对角线全满）
反自反性（主对角线全空）
对称性
反对称性
传递的</p>
<p>一些小tips：不是特别需要记忆。</p>
<ul>
<li>
<p>空关系是反自反的，对称的（不存在元素破坏对称性），也是反对称的（不存在元素破坏反对称性），可传递的。</p>
</li>
<li>
<p><strong>对称性与反对称性不是绝对矛盾的，任何仅含自环的图都满足。</strong></p>
</li>
<li>
<p>对于传递的关系，存在双向边就一定有自环。（因为(a,b)和(b,a)就一定有(a,a)）</p>
</li>
<li>
<p>定量问题：n元素集合上的自反关系有$2^{n^2-n}$个</p>
<blockquote>
<p>从矩阵上来看，选出所有主对角线，剩下  $n^2-n$个元素选或不选</p>
</blockquote>
<p>反自反关系有$2^{n^2-n}$个</p>
<blockquote>
<p>从矩阵上来看，舍弃所有主对角线，剩下 $ n^2-n个$元素选或不选</p>
</blockquote>
<p>对称关系$2^\frac{n^2+n}{2}$个</p>
<blockquote>
<p>从矩阵上来看，n个自环选或不选$2^{n}$，剩下$n^2-n$个元素对应$\frac{n^2-n}{2}$对元素选或不选，选就都选，不选就都不选$2^\frac{n^2-n}{2}$</p>
</blockquote>
<p>反对称关系$2^{n}*3^\frac{n^2-n}{2}$</p>
<blockquote>
<p>从矩阵上来看，n个自环选或不选$2^{n}$，剩下$n^2-n$个元素对应$\frac{n^2-n}{2}$对元素选或不选，选的话从里面挑一个，有两种挑法，不选就都不选，$3^\frac{n^2-n}{2}$</p>
</blockquote>
</li>
</ul>
<p><strong>关系的复合，注意顺序</strong>
关系复合满足结合律，反正是同一个拼凑，先拼哪个无所谓。</p>
<p><strong>重要定理</strong>
传递关系的幂是该关系的子集。
传递 $\longleftrightarrow R^n \subset R 其中n=1，2，3...$
特别的，证明右到左的时候，可以得到<strong>更强的结论</strong>
<strong>即$R^2 \subset R \rightarrow 传递$</strong> <em><strong>判传递常用</strong></em></p>
<blockquote>
<p>证明：$(a,b)\subset R；(b,c)\subset R；(a,c)\subset R^2\subset R$,证毕</p>
</blockquote>
<p>左到右则是利用归纳法，对所有$(a,b)\subset R^{n+1}$可以拆成$(a,x)\subset R^n\subset R;(x,b)\subset R。由于R传递，(a,b) \subset R，R^{n+1}$的每个元素都属于R，推出前者是后者的子集，证毕。</p>
<p>5.2不考</p>
<h4 id="53-%E5%85%B3%E7%B3%BB%E7%9F%A9%E9%98%B5%E4%B8%8E%E5%85%B3%E7%B3%BB%E5%9B%BE">5.3 关系矩阵与关系图</h4>
<p>关系的合成可以等效于矩阵作布尔积
关系幂也就是矩阵幂</p>
<h4 id="54-%E5%85%B3%E7%B3%BB%E7%9A%84%E9%97%AD%E5%8C%85">5.4 关系的闭包</h4>
<p>闭包定义：以最小代价（可以为0）对当前关系R进行扩展使其达到具有某条性质，就称这条性质的闭包。</p>
<p>简单来说，闭包是满足要求性质的最小超集。</p>
<blockquote>
<p>反自反，反对称没有闭包，因为这些是要删元素，而不是加元素。</p>
</blockquote>
<p>自反闭包：扩展至所有自环存在。一般求法是与仅含主对角线的矩阵作并集。</p>
<blockquote>
<p>比如a&lt;b的传递闭包是a&lt;=b</p>
</blockquote>
<p>对称闭包：扩展为对称矩阵。一般求法是$R \bigcup R^{-1}$</p>
<p><strong>传递闭包</strong>：扩展成传递的图（注意并不是整个图必须连通，只需要连通分支传递即可）。即a，b如果联通or有路，就给a，b加一条直接相连的边。
求法是：$\bigcup R^n 的无限并，n=1,2,3...无穷$</p>
<p>下面作详细说明。
传递闭包显然就是要探索出所有的连通关系。根据$R^2$中含有的是在R中的(a,b)(b,c)的(a,c).得出结论 <strong>$R^n$就是路长度确切为n的连通关系，也可以认为是给长度为n的两个点直接加的一条边。</strong>
所有的联通关系显然可以<strong>分划</strong>成路长为1,2,3...的联通。所以结果显然是它们并起来。</p>
<p><strong>任一关系的传递闭包均存在，且唯一</strong>，由数学运算唯一性得证。</p>
<p>此外，由于上述的意义，所以一般不用无穷并，并到 最长路即可。又由于最长路&lt;=顶点个数-1，所以最多取到顶点个数-1.</p>
<h4 id="55-%E7%AD%89%E4%BB%B7%E5%85%B3%E7%B3%BB">5.5 等价关系</h4>
<p>可以抽象某个元素的性质，只关注这个性质进行分类。比如 按被4整除的余数分类，只会分成0 ，1 ，2 ，3 四类。并不关系元素抽象前的特征。</p>
<p><strong>等价关系:(证明常用)自反，对称，传递。</strong>
空关系是反自反的，不是等价关系。同余是等价关系。</p>
<p>上述阐述的类 就是等价类。<strong>等价类可以用并查集来理解</strong>
<strong>一个类用一个代表元a来表征</strong>，这个代表元a可以任选在这个类中的元素即可。<strong>a的等价类就是所有与a有关系的元素的集合（包括a本身）。</strong>
<em>像并查集的祖先可以任选。且不同类一定没有关系</em></p>
<p>显然有以下性质：
a与b有关系$\longleftrightarrow$(a,b)属于R$\longleftrightarrow$a的等价类=b的等价类$\longleftrightarrow$a的等价类，b的等价类交集非空
<em>这不就纯纯并查集。(a,b)属于R就相当于进行了merge操作。我还知道交集为空一定不是同一个等价类呢</em></p>
<p><strong>R的等价类构成S集合的一个划分。S集合的一个划分也可以构造R的等价关系</strong>
证明：
前者证明：证明划分的性质：1.两两交集为空，2.并起来是本身
后者证明：证明等价关系：得到一个关系R{(x,y)|x,y均属于$A_i$},证明它自反对称传递。</p>
<blockquote>
<p>$A_i$是划分的第i块。</p>
</blockquote>
<h4 id="56-%E5%81%8F%E5%BA%8F%E5%85%B3%E7%B3%BB">5.6 偏序关系</h4>
<p><strong>偏序关系:(证明常用)自反，反对称，传递。</strong>
典题：证明大于等于是偏序；整除是偏序；大于不是偏序。</p>
<p>通俗来说：偏序关系是任何存在单向关系并且带等号。</p>
<p>偏序的英文翻译是“partial order”，即<strong>部分的顺序</strong>。即<strong>某些元素之间可能是不可比的。</strong>
比如对于整除这个偏序，3和5无法比较。</p>
<p>由此，如果每对元素都可以比，就称为<strong>全序</strong>。（注意，全序只是偏序的一种）
<strong>良序：全序的情况下有确切的起点（即最小元）</strong>。良序可以没有终点。</p>
<blockquote>
<p>良序一定是全序，有限全序一定是良序</p>
</blockquote>
<p><strong>哈塞图</strong>：表示偏序关系的图，并且只体现必要的边（或者可以说只体现覆盖关系）。
覆盖关系：属于偏序关系并且相邻（即不存在中间态连接它们）。</p>
<p>作哈塞图的两种方法</p>
<ol>
<li>做出偏序关系，然后删边</li>
<li><strong>从小到大列出覆盖关系，直接画出覆盖关系。</strong>
例子见P251</li>
</ol>
<p><strong>极大元与极小元</strong>：良序中唯一，非良序一般<strong>由于某些不可比可能不唯一。</strong></p>
<blockquote>
<p>这里的定义是，不存在比我大的，我就是极大。</p>
</blockquote>
<p><strong>最大元与最小元</strong>：可能不存在，存在即唯一。</p>
<blockquote>
<p>这里的定义是，我必须比所有人大。所以一旦有不可比就不存在最大元。</p>
</blockquote>
<p>上界，最小上界，下界，最大下界：easy.</p>
<h2 id="%E5%9B%BE">图</h2>
<h4 id="62-%E6%8F%A1%E6%89%8B%E5%AE%9A%E7%90%86-%E4%BA%8C%E5%88%86%E5%9B%BE-%E4%B8%80%E4%BA%9B%E6%A6%82%E5%BF%B5">6.2 握手定理 二分图 一些概念</h4>
<p>应用图论<strong>解决实际问题的时候，说明建模过程。</strong></p>
<p><strong>握手定理</strong>：一条边带来两个度（1入度1出度）。</p>
<ul>
<li><strong>用来解决类似鸽巢原理类的问题。</strong>
典题：n只球队，进行了n+1场比赛，一定存在球队进行了3场比赛。
<blockquote>
<p>建图，度为2n+2，分给n个点，由于鸽巢原理，一定有度为3的点。</p>
</blockquote>
</li>
<li>奇偶性限制：总度数为偶数；奇度数顶点一定为偶数个。</li>
</ul>
<p><strong>二分图</strong>：图的一种性质，是可二分的就称是二分图。
通俗来说，可以画成河的两岸，每一条边都是桥梁。同一个河岸直接不能沟通。</p>
<p><strong>可以用种类并查集来理解，把边设为是对立关系。</strong>
得到我对立的对立就是我的朋友。但是我和我的朋友不对立，所以没有边。
由此得到一些性质：</p>
<ul>
<li><strong>不存在长度为奇数的回路</strong>（对立关系必须走偶数次才能抵消）
<blockquote>
<p><strong>二分图的充要条件就是 所有回路长度均偶数。</strong></p>
</blockquote>
</li>
<li>子图不是二分图，原图一定不是二分图。（长度为奇数的回路不会消失）</li>
<li><strong>二分图可以等价成分块矩阵</strong>(即按两岸分块，那么同岸就一定是0矩阵)</li>
</ul>
<p>$$
\begin{bmatrix}
0&amp;B\
A&amp;0
\end{bmatrix}
$$</p>
<ul>
<li><strong>二分图还可以用图着色的来判定。用两种颜色染色，相邻点不同色（充要）</strong></li>
</ul>
<br>
<br>
<br>
<p><strong>二分图的匹配</strong>：以男女之间暧昧关系为例，匹配就是按一夫一妻制结婚的结果。
最大匹配：结出最多对夫妻。
完全匹配：有序，看相对谁。比如关于女性的一个完全匹配就是保证所有女性都有丈夫。</p>
<p><strong>霍尔婚姻定理</strong>：是否存在完全匹配的充要判定。
对于$(V_1,V_2)$寻找一个关于$V_1$的完全匹配，只需要保证对于$V_1$的所有子集A都满足，$|A|&lt;=|N(A)|$。同样拿上述例子。就是要保证，<strong>选出来的任一数量的女性组合，与她们有暧昧关系的男生总数要大于等于这群女性的数量。</strong></p>
<p>运用该定理一般较为繁琐，需要枚举所有子集。
<br></p>
<br>
<p>补图：点集相同，边集互补。
子图：点集，边集都是子集。
真子图：点集，边集都是子集。且不是原图。</p>
<p>生成子图:点集相同，只删边。
导出子图：原图删点之后把无端边也相应删了。
并图：两图点集并，边集并。</p>
<p>useless
边的收缩：删掉悬挂点的边之后，该点变成孤立，可以将它合成到原来的相连的点(也可以认为把该孤立点删去了)。当然常规情况下也可以收缩，见P278.</p>
<h4 id="63-%E5%9B%BE%E5%90%8C%E6%9E%84">6.3 图同构</h4>
<p><strong>证明图同构</strong>的方法（本质一样）：</p>
<ol>
<li>（不常用）重画图</li>
<li><strong>构造点集的双射，按边集一一验证相连。</strong>
<blockquote>
<p>这个双射是通过尝试构造的。验证的方法如果规模小直接写，规模大就写成矩阵验证。</p>
</blockquote>
</li>
</ol>
<p><strong>推翻图同构的方法：只需要找到某种性质不同即可。</strong></p>
<ul>
<li>低级推翻： 边数，点数，每个点的度数。</li>
<li><strong>中级推翻： 点与周围点的相邻关系
（比如锁定两个图里面度数相同的点，发现邻居不一样）</strong></li>
<li><strong>高级推翻： 存在一条长度多少的回路/路，特定度数的两个点之间的距离。</strong></li>
<li>特级推翻： 现场发挥</li>
</ul>
<h4 id="64-%E8%BF%9E%E9%80%9A%E6%80%A7">6.4 连通性</h4>
<p>许多概念可以用并查集理解。</p>
<p>割点：删除它，连通分支数量增加（最少增加1，最多无上限）。
割边：删除它，连通分支数量增加（一定增加1，拆桥只能分成两岸）。</p>
<p>连通图的连通分支数量为1。
寻找连通分支：依次dfs，因为一次dfs就会搜完一个连通分支。
<strong>回路中的边一定不是割边，因为可以通过反走来代替。</strong></p>
<p><strong>点连通度：尝试删去最少的点（同时删去该点关联的边），使得原图变为不连通的或者只剩一个点。</strong>
删去的点数就是点连通度。
求点连通度的方法就是从少到多依次尝试。</p>
<p>不连通的图和单点图$K_1$：不用删，点连通度为0
含有割点的连通图和$K_2$：点连通度为1
<strong>$K_n$:点连通度为n-1.特别的对于n个顶点的图，如果点连通度为n-1，则一定是完全图。</strong></p>
<p><strong>边连通度</strong>：类比点连通度理解。
<strong>$K_n$:边连通度为n-1.特别的对于n个顶点的图，如果边连通度为n-1，则一定是完全图。</strong></p>
<blockquote>
<p>$K_n$:边连通度为n-1
证明:删边专门针对一个顶点，显然要删n-1.</p>
<p>对于n个顶点的图，如果边连通度为n-1，则一定是完全图：
反证：如果不是完全图，一定存在度小于n-1的顶点，专门针对这个顶点，边连通度会小于n-1.</p>
</blockquote>
<p>不等式：$$点连通度&lt;=边连通度&lt;=最小度数顶点的度数。$$
很容易证明：如果不连通，则点=边=0；如果连通：删一个点同时至少删了一条关联边。所以对于删去定量的边数时，点数只可能更少。
这就证明：点连通度&lt;=边连通度。
而可以专门针对最小度数顶点进行删边。所以边连通度&lt;=最小度数顶点的度数。</p>
<p>强连通：有向仍连通。
弱连通：化为无向是连通的。</p>
<p>$i,j$两点之间的路的定量关系可以用矩阵幂求得。即5.4传递闭包
最短路：第一次$a_{ij}$不为0的矩阵幂，该幂的值就是最短路长度
路的数目：遍历矩阵幂，把所有$a_{ij}$相加。
不连通：遍历完毕也没出现不为0的$a_{ij}$</p>
<h4 id="65-%E6%AC%A7%E6%8B%89%E8%B7%AF-%E5%93%88%E5%AF%86%E9%A1%BF%E8%B7%AF">6.5 欧拉路 哈密顿路</h4>
<p>欧拉图：存在<strong>欧拉回路</strong>
哈密顿图：存在<strong>哈密顿回路</strong></p>
<p><strong>二者都是一笔画问题。欧拉关注边，哈密顿关注点</strong>。
<br></p>
<p>欧拉回路：<strong>一笔画不重复地经过所有的边，并且闭合</strong>，点可以作为交叉路路口重复经过。</p>
<blockquote>
<p>由于欧拉不关注点，所以非连通图也可以是欧拉图，仅当该图地的连通分支是欧拉图以及若干个孤立点</p>
</blockquote>
<p>欧拉路：<strong>一笔画不重复地经过所有的边，不闭合，头尾分明</strong></p>
<p><strong>欧拉回路充要条件：每个点度数均偶（一进一出）</strong>
<strong>欧拉路   充要条件：含两个奇数度数的点（起点终点），其他均偶。</strong></p>
<blockquote>
<p>欧拉回路起点任选。构造欧拉路则把奇数度数作为起终。</p>
</blockquote>
<br>
<br>
<br>
<p>哈密顿回路：<strong>一笔画不重复地经过所有的点，并且闭合（起点终点可以相同）</strong>。显然边更不能重复经过。边可以不用完。
哈密顿路：<strong>一笔画不重复地经过所有的点，不闭合</strong></p>
<p>哈密顿回路没有充要条件，有一些充分的，和必要的条件。</p>
<p>充分条件：用于判定回路存在，不满足不代表不是。</p>
<ul>
<li><strong>狄拉克定理：如果n&gt;=3，每个顶点的度数至少为n/2，则哈密顿回路存在</strong>
更强结论：欧尔定理</li>
<li><strong>欧尔定理：如果n&gt;=3，任一一对不相邻顶点的度数和至少为n，
即$deg(u)+deg(v)&gt;=n$则哈密顿回路存在</strong></li>
<li>定量分析：如果边数$m&gt;=\frac{n^2-3n+6}{2},$则哈密顿回路存在。</li>
</ul>
<p>必要条件：用于判定回路不存在，满足不代表存在，不满足一定不存在。</p>
<ul>
<li>常用：<strong>哈密顿回路无割点。</strong></li>
<li>更强结论：<strong>删点，哈密顿图G删去s个点后的连通分支数量&lt;=s</strong></li>
</ul>
<blockquote>
<p>可以看出s=1时就是哈密顿回路无割点
证明：G-S的连通分支数&lt;=$G^{'}$-S的连通分支数&lt;=s
$G^{'}$是G删到只剩下一个哈密顿回路的图。故G-S的连通分支数&lt;=$G^{'}$-S的连通分支数（作删去操作的想法是来源于哈密顿图不关注不经历的边，那么极端情况显然这些边是不出现的，还不如我自己删掉考虑极端些。）
而$G^{'}$-S的连通分支数&lt;=s由：一个环被删去s个点，最多会被切成s段</p>
</blockquote>
<h4 id="66-%E6%9C%80%E7%9F%AD%E8%B7%AF">6.6 最短路</h4>
<p>Dij 不必赘述。证明来自归纳+反证法，反证依据是已经被证明了的归纳假设。</p>
<h4 id="67-%E5%B9%B3%E9%9D%A2%E5%9B%BE">6.7 平面图</h4>
<p>平面图是一种性质，交叉图如果可以被平面图表示出来也是平面图。</p>
<p>判平面图：</p>
<ul>
<li><strong>重画它成平面的</strong>。（最直接，最简单）</li>
</ul>
<br>
<br>
<p>判是非平面图：</p>
<ul>
<li><strong>不等式判断</strong>：<strong>若G是平面图，必有$$v&gt;=3时,e&lt;=3v-6$$</strong></li>
<li>推论：<strong>若G是平面图，必有度数不超过5的顶点。</strong></li>
<li>若G是平面图，必有$$没有长度为3的回路，v&gt;=3时,e&lt;=2v-4$$</li>
<li>若G是平面图，必有$$没有长度为3，4的回路，v&gt;=3时,e&lt;=\frac{5}{3}(v-2)$$</li>
<li><strong>操作法</strong>：通过初等细分操作使得包含一个和$K_5$和$K_{3,3}$同胚的子图。
<br>
证明写在之后。</li>
</ul>
<br>
<br>
<br>
<p>欧拉公式: <strong>对于平面表示满足 r=e-v+2.r是区域数量，包括外区域。</strong></p>
<blockquote>
<p>欧拉公式不能用来判平面图，因为要判的显然是交叉图，
而交叉图谁给你平面表示。
其次，该公式可以看作是几何体的欧拉公式把几何体拍扁了使用，损失的维度用外区域来补偿。
2是一个特征值，此处常量为2时，表示是连通平面简单图。</p>
<p>常量为n+1表示有n个连通分支的平面简单图。（证明此只需要对每个连通分支分别使用欧拉公式，然后减去重复计算的外区域。）</p>
</blockquote>
<p>上述一系列证明基于面的度的概念：面的度就是围成该面的边数。
所以<strong>每个面的度至少为3。而 面的度数之和显然是边数的两倍，因为每条边贡献两个面的度</strong>
所以2e&gt;=3r联立欧拉公式消去面r。</p>
<p>如果没有长度为3的回路，每个面的度至少为4，得到2e&gt;=4r.</p>
<p>而如果每个点都度数至少为6，则2e&gt;=6v,这与e&lt;=3v-6矛盾</p>
<br>
<br>
<br>
<p>首先区分一下操作：
<strong>一般删除</strong>：增大平面图的可能。（即平面一定还是平面，而非平面可能删成平面）
一般增加：增大非平面的可能。（同理）
<strong>初等细分：不改变任何平面/非平面的可能（平面一定还是平面，而非平面一定还是非平面）</strong> 见P322。初等细分变换前后称为同胚。</p>
<p>由一般删除/一般增加，可以知道，<strong>子图如果是非平面，则原图一定是非平面</strong>。</p>
<p>所以如果一个图含有某个同胚于非平面的子图，则子图非平面，则原图也非平面。</p>
<h4 id="68-%E5%9B%BE%E7%9D%80%E8%89%B2">6.8 图着色</h4>
<p><strong>四色定理：平面图的着色数最多为4.</strong>
换而言之，超过4就不是平面图。</p>
<p>一些显然的结论（useless）：</p>
<ul>
<li>$K_n$的着色数是n。</li>
<li>二分图的着色数是2。</li>
<li>圈图的着色数是偶2奇3</li>
</ul>
<h2 id="%E6%A0%91">树</h2>
<h4 id="71-%E6%A0%91%E5%85%A5%E9%97%A8">7.1 树入门</h4>
<p>树的定义：树是没有简单回路的连通无向图。</p>
<ul>
<li>树是n点n-1条边（充要）。
<blockquote>
<p>证明：n-1边没有回路。另一个方向用强归纳法，对k+1删去1条边得到两个满足归纳假设的小树，加和得证。</p>
</blockquote>
</li>
<li>每条边都是割边。</li>
<li>一定是平面图。</li>
<li>任两点路径唯一（充要）。
<blockquote>
<p>证明：唯一说明连通,唯一说明无环，否则假设有环，环一定可以拆成两条路。
另一个方向：假设不唯一，那么两条路可以合成一个环，与树矛盾，证毕。</p>
</blockquote>
</li>
</ul>
<p><strong>正则m叉树：每个结点要么没有孩子，要么有m个孩子。</strong></p>
<blockquote>
<p>有k个非叶子结点的正则m叉树总共有m*k+1个结点。因为有k个父亲，每个父亲有m个孩子，则总孩子数量是m*k（计算的都是孩子，没有重复计算），根节点没有作为孩子被计算，所以+1.</p>
</blockquote>
<p>平衡树：任一对叶子结点相差的层数不超过1.</p>
<h4 id="72-%E5%93%88%E5%A4%AB%E6%9B%BC%E6%A0%91">7.2 哈夫曼树</h4>
<p>前缀码：一个字母的比特串永远不出现在另一个的开头部分。</p>
<blockquote>
<p>从树上来看，也就是说，不会存在 某条没有达到叶子节点的是合法编码（否则它被 从当前继续往下走的所包含），也就是说<strong>所有编码一定到达叶子节点</strong>。</p>
</blockquote>
<p>已知前缀码二叉树，和密码，解码方法:按照密码走，走到叶子就回到根。多次循环剖分成多个字符串。</p>
<p>如何构造前缀码二叉树？<strong>哈夫曼树</strong>
每一步把最小总权值的两个树合成一个树（权值相加，并在之后的操作中就等效成一个树来看），左大右小型合成。</p>
<h4 id="74-%E6%9C%80%E5%B0%8F%E7%94%9F%E6%88%90%E6%A0%91">7.4 最小生成树</h4>
<p>简单图是连通的 等价于 含有生成树 。</p>
<blockquote>
<p>证明：树连通，加边更会连通。
连通图如果含有回路总可以删去不影响连通性的边（破圈）。如果没有回路就已经是树啦。</p>
</blockquote>
<p>kruskal（边排序），prim（云结点算法）不必赘述。
最小生成树不一定唯一，但最小生成树对应的权值和一定唯一。</p>
<blockquote>
<p>如果边的权值各不相同，最小生成树唯一。</p>
</blockquote>
<p>拓展：设计一种移除边求最小生成树的算法。
想移除的显然是 边权大的。逆kruskal的思想，把边从大到小排序，依次删去不破坏连通性的边。（因为如果破坏的话，说明这条边必选）</p>

</body>
<script type="text/javascript" src="http://cdn.mathjax.org/mathjax/latest/MathJax.js?config=TeX-AMS-MML_HTMLorMML"></script>
<script type="text/x-mathjax-config"> MathJax.Hub.Config({ tex2jax: {inlineMath: [['$', '$']]}, messageStyle: "none" });</script>
</html>